#include<iostream>
#include<cmath>
#include<chrono>
#include<vector>
using namespace std;
using namespace std::chrono;

int count_primes_brute(int n){
    if(n<2)return 0;
    int count = 0;
    for(int i = 2; i<=n ; i++){
        bool is_prime = true;
        for(int j = 2; j*j<=i ; j++){
            if(i%j==0){
                is_prime=false;
                break;
            }
        }
        if(is_prime) count++;
    }
    return count;
}

int main(){
    int n;
    cout<<"请输入正整数n：";
    cin>>n;
    auto start1 = high_resolution_clock::now();
    int result1 = count_primes_brute(n);
    auto end1 = high_resolution_clock::now();
    auto duration1 = duration_cast<milliseconds>(end1-start1);
    cout<<result1<<"个素数，耗时："<<duration1.count()<<"毫秒"<<endl;
    system("pause");
    return 0;
}